package sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = new int[]{9, 7, 5, 3, 10, 1, 2, 4, 6, 8};
        mergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public static void mergeSort(int[] a, int l, int r) {
        if (l == r) return;
        if (l + 1 == r) {
            if (a[l] > a[r]) swap(a, l, r);
            return;
        }

        int m = l + (r - l) / 2;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, r);
        merge(a, l, m, r);
    }

    private static void merge(int[] a, int l, int m, int r) {
        if (a[m] <= a[m + 1]) {
            System.out.println("Lucky! No merge needed: left=" + l + ", next=" + r);
            return;
        }
        int[] t = new int[r - l + 1];
        for (int i = 0, p = l, q = m + 1; i < (r - l + 1); i++) {
            if (q > r || p <= m && a[p] <= a[q]) {
                t[i] = a[p++];
            } else {
                t[i] = a[q++];
            }
        }
        System.arraycopy(t, 0, a, l, (r - l + 1));
    }

    private static void swap(int[] a, int l, int r) {
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
    }
}
